A PCE working group in an Internet Engineering Task Force (IETF) provides a PCE, in order to solve the problems of multi-domain path computation and complex constraint path of a Multi-Protocol Label Switching/Generalized Multi-Protocol Label Switching (MPLS/GMPLS) network. The PCE is a functional entity specialized in path computation in a network and is configured to compute one optimal path meeting a constraint condition according to a request of a Path Computation Client (PCC) based on the known network topology and constrain condition. The PCE can be located at any position of a network. The PCE can be integrated inside a network device, such as a Label Switch Router (LSR) or an operational support system, and can also be an independent device. A special PCE computation protocol (PCE Communication Protocol, abbreviated as PCEP) can be adopted to conduct communications between a PCC and a PCE and between two PCEs, for example, submitting a path computation request and acquiring a path computation result. The PCC can be an LSR or a Network Management System (NMS) in the MPLS/GMPLS network.
In the PCEP, the format of a notification message for the PCE (called a PCEP notification message, hereafter referred to as a PCNtf message) is as follows.
<PCNtf Message> ::= <Common Header>         <notify-list><notify-list> ::= <notify> [<notify-list>]<notify> ::= [<request-id-list>]     <notification-list><request-id-list> ::= <RP>[<request-id-list>]<notification-list> ::= <NOTIFICATION>[<notification-list>]
The Request Parameter (RP) object contains a request number, with the format shown in FIG. 1. The format of the NOTIFICATION object is as shown in FIG. 2, in which a flag bit, a Notification-type, a notification value and an optional Type Length Value (TLV) are specified, wherein there are two Notification-types:
Notification-type=1: cancel a path computation request;
Notification-type=2: overloaded PCE.
According to the definition of the RFC 4655 of the IETF standard, the PCE can be classified as a stateful PCE and a stateless PCE. The stateless PCE performs path computation only using information in a Traffic Engineering Database (TED), while the stateful PCE performs path computation not only based on topological information in the TED but also using information of known paths and occupied resources in the network. Therefore, the stateful PCE can solve the difficult problem of the stateless PCE well, which is described in the following scenarios in detail.
Scenario 1: a resource conflict is caused by batch establishment.
Scenario 1.1: when a failure occurs in the network, multiple Label Switched Paths (LSPs) need to be restored at the same time in a single domain and multiple domains.
Under the architecture of the PCE, a lot of LSP computation requests are received by the PCE in a short time to request for computation to restore LSPs when a failure occurs in the network. For example, when a node fails, all the LSPs passing through the node and initiated/ended from the node fail. At the moment, the failed LSPs request the PCE to re-compute the route of new restored LSPs. In this case, these requests are sent to the PCE at a very short time interval. After completing the computation of the computation request received earlier, the PCE must lock or reserve these resources, otherwise, these resources are regarded to be idle and are further used in the path computations performed in response to the subsequent computation requests, so as to result in a resource conflict. The scenario exists in the computation for the restored path in a single-domain or a multi-domain network.
Scenario 1.2: batch routing computation is executed.
When needing to execute batch routing computation but not having concurrent computation capability, the PCE needs to execute multiple computations in series. Like the scenario above, a resource conflict may occur.
Scenario 2: computation results need to be synchronized in time when multiple PCEs cooperate.
Scenario 2.1: multi-domain computation is solved by a multi-PCE cooperative architecture using a Backward Recursive PCE-based Computation (BRPC).
When the multi-PCE cooperation and the BRPC algorithm are adopted, computation is started from the domain where the destination node is located. The optimal path from each entrance node to the destination node is computed in each domain, then, a set of computed paths is transmitted to an adjacent upstream PCE, and finally, an optimal end-to-end path is generated after the computation in a head domain.
Therefore, for an intermediate domain and a tail domain except for the head domain, if there are N entrance boundary nodes in a certain domain, N potential paths may be returned to the upstream domain after the computation in the domain is completed, and only one of the N paths is taken after the final end-to-end computation is successful.
Therefore, after the computation in each domain is completed, a resource conflict may also occur if the computation result is not saved.
Scenario 2.2: a multi-domain computation is solved by the multi-PCE cooperative architecture using a hierarchical PCE.
When cross-domain or cross-layer computation is solved by a hierarchical PCE, multiple sub-domains form one parent domain. Each sub-domain has a corresponding PCE. The PCE in the parent domain maintains interconnection information of sub-domains which is used for computing a domain sequence. Each sub-domain in the parent domain is abstracted into a node. The PCE of each sub-domain needs to establish a session with the PCE in the parent domain and reports connectivity with other domains to the PCE in the parent domain. Therefore, the PCE in the parent domain can acquire the connectivity of all the sub-domains and can compute the domain sequence.
During the computation of a cross-domain path, the parent domain receives a computation request and computes the domain sequence, and then, sends the request to each sub-domain in the domain sequence. When the computation in all the sub-domains is completed, the parent domain collects the computation results in all the sub-domains, splices the computation results to generate an end-to-end path computation result and returns the computation result to a PCC.
Therefore, when the computation in part of the sub-domains is successful, the computation results need to be saved, otherwise, a resource conflict may occur. Furthermore, after the end-to-end computation is completed, it is necessary to notify each PCE participating in the computation to update the resources, otherwise, a resource conflict may still occur, this is because the computation in some domains is successful but the computation in other domains is unsuccessful.
Scenario 2.3: a resource conflict occurs among multiple PCEs during a multi-domain computation.
In the scenario in which multiple PCEs cooperate to solve a cross-domain computation, when there are two domains A and B, a PCE is deployed in each domain respectively. The PCEs in the domains A and B create LSPs at the same time, wherein the head node and the tail node of one LSP1 are in the A domain and B domain respectively, while the head node of another LSP2 is in the B domain. If a resource conflict may occur in LSP2, the LSP updates the resources in PCE1 but the notification message about the updating is not sent to a downstream PCE, while PCE3 also updates the resources in LSP2 at the moment, thereby, the resources of LSP1 may be used.
Scenario 3: the PCE is synchronized with network resources.
After the PCE completes the path computation, the LSR in the network establishes or deletes an LSP in the subsequent signalling process. After the LSP is established or deleted successfully, it is necessary to notify the PCE of the new occupation condition of the network resources at once. If the notification is not given, the link state is flooded by an Internet Gateway Protocol (IGP). In the period between the successful establishment of the connection and the synchronization of the TEDs of all the LSRs in the whole network completed by flooding, a resource conflict may also occur as data in the TED of the PCE are not consistent with that in the TEDs of the LSR nodes in the network.
It can be seen from what described in the scenarios above that the stateful PCE performs path computation not only based on the topological information in the TED but also using the information of the known paths and occupied resources in the network, so as to avoid the resource conflict. However, the computation accuracy of the stateful PCE mainly depends on the accuracy of the information, such as the occupied resources and the computation results, which the stateful PCE is aware of, but the amount of information which the stateful PCE is aware of is very limited at present, as a result, the resource conflict may still occur even the path computation is performed by the stateful PCE.